package algorithm.dynamic_programming;

import java.util.ArrayList;
import java.util.List;

public class LeetCode118_YangHuiTriangle {

    // 杨辉三角
    public static List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> result = new ArrayList<>(numRows);
        //从第1行开始遍历
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> element = new ArrayList<>();
            //第一行和第二行进行特殊处理
            if (i == 0){
                element.add(1);
                result.add(element);
            }
            if (i == 1){
                element.add(1);
                element.add(1);
                result.add(element);
            }
            //第三行开始
            if (i > 1){
                //第一个元素必定是1
                element.add(1);
                //中间的元素是上一行的左右元素之和
                for (int k = 1; k < i; k++) {
                    element.add(result.get(i-1).get(k-1) + result.get(i-1).get(k));
                }
                //最后一个元素必定是1
                element.add(1);
                result.add(element);
            }
        }
        return result;
    }


}
